{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Array Pairs Divisible by K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计可以被 K 整除的下标对数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组 <code>nums</code> 和一个整数 <code>k</code> ，返回满足下述条件的下标对 <code>(i, j)</code> 的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt;= n - 1</code> 且</li>\n",
    "\t<li><code>nums[i] * nums[j]</code> 能被 <code>k</code> 整除。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,5], k = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "共有 7 对下标的对应积可以被 2 整除：\n",
    "(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)\n",
    "它们的积分别是 2、4、6、8、10、12 和 20 。\n",
    "其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。    \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4], k = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在对应积可以被 5 整除的下标对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-array-pairs-divisible-by-k](https://leetcode.cn/problems/count-array-pairs-divisible-by-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-array-pairs-divisible-by-k](https://leetcode.cn/problems/count-array-pairs-divisible-by-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[1,2,3,4]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1)/2)+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1)/2)\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        factor = []\n",
    "        p = 1 \n",
    "        while p * p <= k:\n",
    "            if k % p == 0:\n",
    "                factor.append(p)\n",
    "                if p * p < k:\n",
    "                    factor.append(k // p)\n",
    "            p += 1\n",
    "        dic = collections.Counter()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += dic[k // gcd(k, num)]\n",
    "            for f in factor:\n",
    "                if num % f == 0:\n",
    "                    dic[f] += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []\n",
    "        d = 1\n",
    "        while d * d <= k:\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        #  (x1 * x2 ) % k == 0\n",
    "        #  一眼 gcd 好吧\n",
    "        choices = [i for i in range(1, k+1) if k% i == 0]\n",
    "        \n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        m = defaultdict(int)\n",
    "        for x in nums:\n",
    "            v = gcd(x, k)\n",
    "            ans += m[k // v]\n",
    "            for c in choices:\n",
    "                if x % c == 0:\n",
    "                    m[c] += 1\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs0(self, nums: List[int], k: int) -> int:\n",
    "        nm=len(nums)\n",
    "        tot=0\n",
    "        for i in range(nm-1):\n",
    "            for j in range(i+1,nm):\n",
    "                if nums[i]*nums[j]%k==0: tot+=1\n",
    "        return tot\n",
    "\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    ans += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return (lt*(lt-1))//2\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))//2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))//2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return rs\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        factor = []\n",
    "        p = 1 \n",
    "        while p * p <= k:\n",
    "            if k % p == 0:\n",
    "                factor.append(p)\n",
    "                if p * p < k:\n",
    "                    factor.append(k // p)\n",
    "            p += 1\n",
    "        dic = collections.Counter()\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += dic[k // gcd(k, num)]\n",
    "            for f in factor:\n",
    "                if num % f == 0:\n",
    "                    dic[f] += 1 \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnts, ans = Counter(), 0\n",
    "        for num in nums:\n",
    "            g = gcd(num, k)\n",
    "            for c in cnts:\n",
    "                if not (c * g) % k:\n",
    "                    ans += cnts[c]\n",
    "            cnts[g] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return (lt*(lt-1))//2\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))//2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            #sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))//2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return rs\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    res += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num * num % k == 0:\n",
    "                res -= 1\n",
    "        \n",
    "        return res // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        d=Counter()\n",
    "        for v in nums:\n",
    "            d[gcd(v,k)]+=1\n",
    "        \n",
    "        res=0\n",
    "        for k1,v1 in d.items():\n",
    "            for k2,v2 in d.items():\n",
    "                if k1*k2%k==0:\n",
    "                    if k1==k2:\n",
    "                        res+=v1*(v1-1)\n",
    "                    else:\n",
    "                        res+=v1*v2\n",
    "        return res//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnts, ans = Counter(), 0\n",
    "        for num in nums:\n",
    "            g = gcd(num, k)\n",
    "            for c in cnts:\n",
    "                if (c * g) % k==0:\n",
    "                    ans += cnts[c]\n",
    "            cnts[g] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    ans += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        freq = Counter(gcd(num, k) for num in nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for x in freq:\n",
    "            for y in freq:\n",
    "                if x * y % k == 0:\n",
    "                    res += freq[x] * freq[y]\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num * num % k == 0:\n",
    "                res -= 1\n",
    "        \n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            cnt[gcd(v,k)] += 1\n",
    "        ans = 0\n",
    "\n",
    "        for a,b in cnt.items():\n",
    "            for c,d in cnt.items():\n",
    "                if a * c % k == 0: \n",
    "                    ans += b * d\n",
    "        for num in nums:\n",
    "            if num * num % k == 0:\n",
    "                ans -= 1\n",
    "        return ans // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(gcd(n, k) for n in nums)\n",
    "        res = sum(c[g1]*c[g2] for g1, g2 in combinations(c.keys(), 2) if g1*g2 % k == 0)\n",
    "        res += sum(n*(n-1)//2 for g, n in c.items() if g * g % k == 0)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        k1=0\n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            if ki==1:\n",
    "                k1+=1\n",
    "                continue\n",
    "            else :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1))/2+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            #print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1))/2\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        lt=len(nums)\n",
    "        if lt == 1:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return int(lt*(lt-1)/2)\n",
    "        kk=0\n",
    "        \n",
    "        pd=0\n",
    "        rs=0\n",
    "        dk=defaultdict(int)\n",
    "        for i in range(lt):\n",
    "            ki=math.gcd(nums[i],k)\n",
    "            if ki==k:\n",
    "                kk+=1\n",
    "                continue\n",
    "            \n",
    "               \n",
    "               \n",
    "            elif ki>1 :\n",
    "                pd=1\n",
    "                dk[ki]+=1\n",
    "        #print(kk)\n",
    "        rs+=(kk*(kk-1)/2)+(kk*(lt-kk))\n",
    "        if pd:\n",
    "            sorted(dk.items(), key=lambda x: x[0])\n",
    "       \n",
    "            fac=[x[0] for x in dk.items()]\n",
    "            fn=[x[1] for x in dk.items()]\n",
    "            print(rs,fac,fn)\n",
    "           \n",
    "            for i in range(len(fac)):\n",
    "                for j in range(i,len(fac),1):\n",
    "                    if (fac[i]*fac[j])%k ==0:\n",
    "                        if i==j and fn[i]>1:\n",
    "                           rs+=(fn[i]*(fn[i]-1)/2)\n",
    "                        elif i!=j:\n",
    "                           rs+=fn[i]*fn[j]\n",
    "                           #print(i,j,rs)\n",
    "        return int(rs)\n",
    "           \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        f = []\n",
    "        d = 1\n",
    "        while d * d <= k:\n",
    "            if k % d == 0:\n",
    "                f.append(d)\n",
    "                if d * d < k:\n",
    "                    f.append(k // d)\n",
    "            d += 1\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans += cnt[k//gcd(k, x)]\n",
    "            for d in f:\n",
    "                if x % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        divisors = []  \n",
    "        d = 1\n",
    "        while d * d <= k:  # 预处理 k 的所有因子\n",
    "            if k % d == 0:\n",
    "                divisors.append(d)\n",
    "                if d * d < k:\n",
    "                    divisors.append(k / d)\n",
    "            d += 1\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k // gcd(v, k)]\n",
    "            for d in divisors:\n",
    "                if v % d == 0:\n",
    "                    cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        n = 10 ** 5\n",
    "        prime = []\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            if a < b:\n",
    "                a, b = b, a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "        flag = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            if flag[i] == 0:\n",
    "                prime.append(i)\n",
    "            j = 0\n",
    "            while prime[j] * i <= n:\n",
    "                flag[prime[j] * i] = 1\n",
    "                if i % prime[j] == 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        stack = [0] * 1000\n",
    "        stack[0] = 1\n",
    "        counter = [0] * (n + 1)\n",
    "        ret = 0\n",
    "        for x in nums:\n",
    "            i = 0\n",
    "            sright = 1\n",
    "            \n",
    "            g = k // gcd(k, x)\n",
    "            ret += counter[g]\n",
    "            counter[1] += 1\n",
    "            while prime[i] * prime[i] <= x:\n",
    "                p = 1\n",
    "                tmp = sright\n",
    "                while x % prime[i] == 0:\n",
    "                    x //= prime[i]\n",
    "                    p *= prime[i]\n",
    "                    for j in range(tmp):\n",
    "                        stack[sright] = t = p * stack[j]\n",
    "                        counter[t] += 1\n",
    "                        sright += 1\n",
    "                i += 1\n",
    "            if x != 1:\n",
    "                for j in range(sright):\n",
    "                    counter[stack[j] * x] += 1\n",
    "            # print(g, counter[:8], ret)\n",
    "        return ret     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "pt=PrimeTable(10**5+5)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        cnt=Counter()\n",
    "        for x in nums:\n",
    "            res+=cnt[k//gcd(k,x)]\n",
    "            for i in pt.get_factors(x):\n",
    "                cnt[i]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个数的所有因子，时间复杂度 O(MlogM)\n",
    "M = 100001\n",
    "divisors = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i, M, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += cnt[k // gcd(num, k)]\n",
    "            for x in divisors[num]:\n",
    "                cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1,MX):\n",
    "    for j in range(i,MX,i):\n",
    "        divisors[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            ans += cnt[k/gcd(num,k)]\n",
    "            for d in divisors[num]:\n",
    "                cnt[d]+=1\n",
    "            # print(k/gcd(num,k),cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            ans += cnt[k // gcd(x, k)]\n",
    "            for i in divisors[x]:\n",
    "                cnt[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "数学\n",
    "nums[i] * nums[j] % k === 0\n",
    "固定nums[j], 统计nums[i]\n",
    "首先将nums[j] 和 k进行约分\n",
    "nums[i] * (nums[j] / gcd(nums[j], k)) % (k / gcd(nums[j], k)) === 0\n",
    "nums[i] 必须是x = k / gcd(nums[j], k) 的倍数\n",
    "预处理出每个数的因子 \n",
    "哈希表统计每个数的每个因子出现的次数, 对于固定nums[j],cnt[x]即为答案\n",
    "map统计nums[i]各因子出现的次数, 每次加1就变成了当前因子的倍数的个数++\n",
    "\"\"\"\n",
    "MX = 100001\n",
    "div = [[] for _ in range(MX)]\n",
    "for i in range(1, MX): # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        div[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, A: List[int], k: int) -> int:\n",
    "        res, c = 0, Counter()\n",
    "        for x in A:\n",
    "            res += c[k // gcd(x, k)]\n",
    "            for d in div[x]: c[d] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 100010\n",
    "f = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i, M, i):\n",
    "        f[j].append(i)\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans += cnt[k//gcd(k, x)]\n",
    "            for v in f[x]:\n",
    "                cnt[v] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):  # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "from math import gcd\n",
    "\n",
    "# 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5\n",
    "MX = 100001\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0  # 存储满足条件的下标对的数量\n",
    "        cnt = Counter()  # 存储因子出现的次数\n",
    "        \n",
    "        # 遍历数组nums\n",
    "        for v in nums:\n",
    "            # 对于每一个数v，检查有多少先前出现的数与之乘积能被k整除\n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            \n",
    "            # 更新因子出现的次数\n",
    "            for d in divisors[v]:\n",
    "                cnt[d] += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100001\n",
    "div = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i, MX, i):\n",
    "        div[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for v in nums:\n",
    "            \n",
    "            ans += cnt[k / gcd(v, k)]\n",
    "            for d in div[v]:\n",
    "                # d是v的因子 也就是说d的倍数随着遍历到v 会增加1\n",
    "                cnt[d] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumberTheoryAllFactor:\n",
    "    def __init__(self, ceil):\n",
    "        self.ceil = ceil + 100\n",
    "        self.factor = [[1] for _ in range(self.ceil + 1)]\n",
    "        self.get_all_factor()\n",
    "        return\n",
    "\n",
    "    def get_all_factor(self):\n",
    "        # 模板：计算 1 到 self.ceil 所有数字的所有因子\n",
    "        for i in range(2, self.ceil + 1):\n",
    "            x = 1\n",
    "            while x * i <= self.ceil:\n",
    "                self.factor[x * i].append(i)\n",
    "                x += 1\n",
    "        return\n",
    "    \n",
    "nt = NumberTheoryAllFactor(10**5)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        dct = defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            w = k // math.gcd(num, k)\n",
    "            ans += dct[w]\n",
    "            for w in nt.factor[num]:\n",
    "                dct[w] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx=100001\n",
    "g=defaultdict(list)\n",
    "for i in range(1,mx):\n",
    "    for j in range(i,mx,i):\n",
    "        g[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter()\n",
    "        res=0\n",
    "        for v in nums:\n",
    "            res+=cnt[k//gcd(k,v)]\n",
    "            for i in g[v]:\n",
    "                cnt[i]+=1\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
